package com.nowcoder.arithmetic;

import java.util.Scanner;

/**
 * 有 n 个学生站成一排，每个学生有一个能力值，牛牛想从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k
 * 个学生的能力值的乘积最大，你能返回最大的乘积吗？ 输入描述: 每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50)，表示学生的个数，接下来的一行，包含
 * n 个整数，按顺序表示每个学生的能力值 ai（-50 <= ai <= 50）。接下来的一行包含两个整数，k 和 d (1 <= k <= 10, 1 <= d <= 50)。
 *
 *
 * 输出描述: 输出一行表示最大的乘积。
 *
 * 输入例子:  3
 *         7 4 7
 *         2 50
 *
 * 输出例子: 49 User: Ruijie Date: 2016/8/8
 */
public class Chorus {

    //定义两个矩阵
    //dpMax[i][k]表示必须以i结尾的选择k个数的最大值，dpMax[i][j]=Max{dpMax[i][j],dpMax[j][k-1]*arr[i]}(j<i&&i-j<=d)
    //dpMin[i][k]表示必须以i结尾的选择k个数的最小值，dpMin[i][j]=Max{dpMin[i][j],dpMin[j][k-1]*arr[i]}(j<i&&i-j<=d)
    public static long Chorus(int[] arr, int k, int d) {
        long[][] dpMax = new long[arr.length][k+1];
        long[][] dpMin = new long[arr.length][k+1];
        long maxResult = arr[0];
        //初始化以i结尾选择0个元素的最大乘积和最大乘积
        for (int i = 0; i < arr.length; i++) {
            dpMax[i][0] = 1;
            dpMin[i][0] = 1;

        }
        //初始化以i结尾选择1个元素的最大乘积和最小乘积
        for(int i=0;i<arr.length;i++){
            dpMax[i][1]=arr[i];
            dpMin[i][1]=arr[i];
            maxResult=Math.max(maxResult,arr[i]);
        }
        for(int i=1;i<arr.length;i++){
            for(int j=2;j<=k;j++){
                for(int m=i-1;m>=Math.max(i-d,0);m--){
                    dpMax[i][j]=Math.max(dpMax[i][j],Math.max(dpMax[m][j-1]*arr[i],dpMin[m][j-1]*arr[i]));
                    dpMin[i][j]=Math.min(dpMin[i][j],Math.min(dpMin[m][j-1]*arr[i],dpMax[m][j-1]*arr[i]));
                }
                maxResult=Math.max(maxResult,Math.max(dpMax[i][j],dpMin[i][j]));
            }

        }
        return maxResult;
    }
    public static long solve(int[] student, int selectK, int difLess) {
        long[][] maxMul = new long[student.length][selectK + 1];
        long[][] minMul = new long[student.length][selectK + 1];
        long maxResult = student[0];
        for (int i = 0; i < maxMul.length; i++) {
            maxMul[i][0] = 1; // 初始化为1
            minMul[i][0] = 1; // 初始化为1
        }

        for (int i = 0; i < maxMul.length; i++) {
            maxMul[i][1] = student[i];
            minMul[i][1] = student[i];
            if(student[i] > maxResult){maxResult = student[i];}
        }
        for (int k = 2; k < maxMul[0].length; k++) {
            for (int i = 0; i < maxMul.length; i++) {
                long tempMax , tempMin, curMax = Integer.MIN_VALUE, curMin = Integer.MAX_VALUE;
                if (i < k - 1 ) {
                    maxMul[i][k] = 1;
                    minMul[i][k] = 1;
                } else {
                    for (int j = k - 2; j < maxMul.length; j++) {
                        if (j >= i - difLess && j < i) {
                            tempMax = maxMul[j][k - 1] * student[i];
                            tempMin = minMul[j][k - 1] * student[i];
                            curMax = Math.max(curMax, Math.max(tempMax, tempMin));
                            curMin = Math.min(curMin, Math.min(tempMax, tempMin));
                        }
                        maxMul[i][k] = curMax;
                        minMul[i][k] = curMin;
                        maxResult = Math.max(maxResult, curMax);
                    }
                }
            }
        }
        return maxResult;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int len = scanner.nextInt();
            int[] arr = new int[len];
            for (int i = 0; i < len; i++) {
                arr[i] = scanner.nextInt();
            }
            int k = scanner.nextInt();
            int d = scanner.nextInt();
            System.out.println(Chorus(arr, k, d));
        }
       // int[] arr={7,4,7};
        //int[] arr1={7, -15, 31, 49, -44, 35, 44, -47, -23, 15, -11, 10, -21, 10, -13, 0, -20, -36, 22, -13, -39, -39, -31, -13, -27, -43, -6, 40, 5, -47, 35, -8, 24, -31, -24, -1};
        //int[] arr2={-41, -5, -10, -31, -44, -16, -3, -33, -34, -35, -44, -44, -25, -48, -16, -32, -37, -8, -33, -30, -6, -18, -26, -37, -40, -30,-50, -32, -5, -41, -32, -12, -33, -22, -14 ,-34 ,-1 ,-41, -45, -8, -39, -27, -23, -45, -10 ,-50 ,-34};
       // int[] arr3={-23,-14,-35,-45,-43,-67,-23,-12};
        //System.out.println(Chorus(arr,2,50));
        //System.out.println(solve(arr,2,50));
        //System.out.println(Chorus(arr1,3,31));
       // System.out.println(solve(arr1,3,31));
        //System.out.println(Chorus(arr2,6,3));
       // System.out.println(solve(arr2,6,3));
        //System.out.println(solve(arr3,8,1));
        //System.out.println(Chorus(arr3,8,1));
    }

}
